Originally, cable networks were established to provide TV signals to a community that otherwise could not receive reliable TV signals. With subsequent addition of more channels, cable TVs have gained enormous popularity in the general segment as well. With the advent of the Internet and other digital communications, however, cable networks and channels have become a focus for transmitting digitized information at high speed and bandwidth. This is because a cable network can provide a high speed digital communication channel in addition to well known traditional cable services.
In cable networks, cable modems provide high speed data transporting functions between a cable network and a connected user. Cable modems typically implement a forward error correction (FEC) scheme. Prior Art FIG. 1 illustrates a conventional cable modem transmission block diagram 100 depicting an FEC scheme that complies with the standard of ITU-T Recommendation J-83 Annex B. The ITU-T Recommendation J-83 Annex B specifies using 64- and 256-quadrature amplitude modulation (QAM). The cable transmission block diagram 100 includes an FEC encoder 102, an FEC decoder 104, and a cable channel 106. The FEC encoder 102 encodes data using conventional FEC schemes for transmission to the FEC decoder 104 through the cable channel 106.
The FEC encoder 102 includes a Reed Solomon (RS) encoder 108, a convolutional interleaver 110, a randomizer 112 (e.g., scrambler), and a Trellis coded modulation (TCM) encoder 114. The RS encoder 108 sequentially receives 122 byte (i.e., symbol) packets with each byte containing 7 bits. Each packet contains 122 7-bit symbols or bytes. The RS encoder 108 adds six 7-bit redundancy bytes for correcting up to 3 symbol errors. The RS encoded 128 7-bit symbol packets are then transmitted to the interleaver 110 for convolutionally interleaving the symbols by modifying the order of the symbols in a packet. Convolutional interleaving is designed to reduce burst mode errors.
The interleaver 110 sequentially transmits the RS encoded and interleaved 128 7-bit symbol packets to the randomizer 112. The randomizer 112 adds a pseudorandom noise sequence of 7 bit symbols by performing bit-wise exclusive-OR operations to the symbols in an FEC frame (e.g., packet) to assure a random transmitted sequence. As used herein, an FEC frame refers to a packet that is processed in sequential fashion in the FEC encoder 102 and FEC decoder 104. The randomizer 112 thus provides even distribution of symbols in the constellation (e.g., 64 QAM, 256 QAM) to enable the modem to maintain proper phase lock during the transmission of data.
The randomized data packets, each of which includes 128 7-bit symbols, are then serially transmitted to the TCM encoder 114. As will be discussed below, the TCM encoder 114 adds redundancy to the data to improve the signal-to-noise ratio by increasing the symbol constellation without increasing the symbol rate. The TCM encoded data is then sent to the FEC decoder 104 over the cable channel 106. The conventional FEC encoder 102 including the RS encoder 108, the interleaver 110, the randomizer 112, and the TCM encoder 114 is known in the art and is described, for example, in a standard recommended by ITU-T (International Telecommunication Union) Recommendation J.83 entitled "Digital Multi-Programme Systems for Television Sound and Data Services for Cable Distribution," which is incorporated herein by reference in its entirety. For example, the ITU-T Recommendation J.83 specifies a single chip 64/256-QAM TCM encoder, which may be used to encode the inner code for a concatenated decoding scheme of North American cable modem.
The FEC decoder 104 includes a TCM decoder 116, a de-randomizer 118, a convolutional de-interleaver 120, and an RS decoder 122. The TCM decoder 116 receives the data serially from the FEC encoder 102 via the cable channel 106 and decodes the TCM encoded data. The TCM decoded data is then transmitted to the de-randomizer 118 and de-randomizes the symbols in the 128 7-bit symbol packets. After de-randomizing, the convolutional de-interleaver 120 receives the de-randomized data and de-interleaves the symbols in the 128 7-bit symbol packets. The de-interleaver 120 then transmits the de-interleaved data to the RS decoder 116.
The RS decoder 116 decodes the received data by performing RS error detection and correction on the received data. This RS decoding removes the 6 7-bit redundancy symbols added by the RS encoder 108 and thereby generates the original MPEG framed data of 122 7-bit symbol or byte packets as output.
The concatenated FEC coding scheme described in the ITU-T standard employs trellis coding for the inner code. The use of the trellis coding introduces redundancy to improve the signal-to-noise ratio by increasing the symbol constellation without increasing the symbol rate. Such coding is referred to as "trellis coded modulation" or "TCM" for short.
Prior Art FIG. 2A illustrates a block diagram of a conventional TCM encoder 114. The TCM encoder 114 of Prior Art FIG. 2 is a 64-QAM TCM encoder, which encodes a group of four RS encoded symbols into five consecutive 64-QAM symbols for mapping into five consecutive 64 QAM signals. The 64-QAM TCM encoder 114 serially receives 128 7-bit FEC frames (e.g., packets). A parser 202 identifies a group of four 7-bit symbols as RS1, RS2, RS3, and RS4 and assigns the symbols RS1 and RS2 as in-phase "I" component and assigns the symbols RS3 and RS4 as quadrature "Q" component. The symbol RS1 includes seven bits I.sub.0, I.sub.1, I.sub.2, I.sub.3, I.sub.4,I.sub.5, and I.sub.6 ; the symbol RS2 includes bits I.sub.7, I.sub.8, I.sub.9, I.sub.10, I.sub.11, I.sub.12, and I.sub.13 ; RS3 includes 7 bits Q.sub.0, Q.sub.1, Q.sub.2, Q.sub.3, Q.sub.4, Q.sub.5, and Q.sub.6 ; and RS4 includes bits Q.sub.7, Q.sub.8, Q.sub.9, Q.sub.10, Q.sub.11, Q.sub.12, and Q.sub.13. Since each symbol contains 7 bits, the total number of input bits for the four symbols is 28 bits with 14 bits each for I and Q symbols.
In this parsing scheme, the parser 202 assigns the individual bits of the I and Q symbols RS symbols into two groups as follows: two upper or most significant uncoded bit streams 212 and 214 and one lower or least significant bit coded bit stream 206 and 208. For the I component, the parser 202 outputs two upper uncoded bit streams 212: one stream including bits I.sub.1, I.sub.4, I.sub.7, I.sub.10, and I.sub.12, and the other stream including bits I.sub.2, I.sub.5, I.sub.8, I.sub.11, and I.sub.13. For the lower coded bit stream 216 of the I component, the parser 202 outputs the bits I.sub.0, I.sub.3, I.sub.6, and I.sub.9 for transmission to a differential encoder 204.
Likewise, for the Q component, the parser 202 outputs two upper uncoded bit streams 214: one stream including bits Q.sub.1, Q.sub.4, Q.sub.7, Q.sub.10, and Q.sub.12, and the other stream including bits Q.sub.2, Q.sub.5, Q.sub.8, Q.sub.11, and Q.sub.13. For the lower coded bit stream 218 of the Q component, the parser 202 outputs the bits Q.sub.0, Q.sub.3, Q.sub.6, and Q.sub.9 for transmission to the differential encoder 204. The two upper uncoded bit streams 212 and 214 of I and Q components are transmitted to a 64-QAM mapper 210.
With reference still to Prior Art FIG. 2A, the differential encoder 204 receives the lower streams 216 and 218 of I and Q components in sequence and performs a 90 degree rotationally invariant trellis coding for each corresponding pair of I and Q bits as received. Specifically, the differential encoder 204 performs the rotationally invariant trellis coding for the I and Q bit pairs as they are received as follows: I.sub.0 and Q.sub.0, I.sub.3 and Q.sub.3, I.sub.6 and Q.sub.6, and I.sub.9 and Q.sub.9. This allows the information to be carried by the change in phase, rather than by the absolute phase. The differential encoder 204 then transmits the differentially encoded lower stream I and Q components to a pair of punctured binary convolutional encoders 206 and 208, respectively.
The punctured binary convolutional encoders 206 and 208 are rate 1/2 binary convolutional encoders and convolutionally encodes redundancy into the least significant bits of the I and Q symbols to improve signal-to-noise gain. The convolutional encoders 206 and 208 are 16-state non-systematic 1/2 rate encoders with the generator: G1=010 101 and G2=011 111 (25, 37) octal. This generator is equivalent to the generator matrix [1.sym.D.sup.2.sym.D.sup.4, 1.sym.D.sym.D.sup.2.sym.D.sup.3.sym.D.sup.4 ], where D represents a delay element "Z.sup.-1." The 1/2 rate encoder generates 8 output bits from the four input bits for each lower I and Q component streams 216 and 218.
The 8 output bits are fed into a puncture matrix: 0001 1111, where "0" denotes NO transmission and "1" represents transmission of the output signal. The puncture matrix essentially converts the rate 1/2 encoder to rate 4/5 to produce a single serial bit stream of 5 bits. Accordingly, the punctured binary convolutional encoders 206 and 208 encodes the 4 bits of the lower I and Q bit streams 216 and 218, respectively, to generate 5 coded bits of I.sub.0 ', I.sub.1 ', I.sub.2 ', I .sub.3 ', and I.sub.4 ' as the convolutionally encoded lower I stream 220 and 5 coded bits of Q.sub.0 ', Q.sub.1 ', Q.sub.2 ', Q.sub.3 ', and Q.sub.4 ' as the convolutionally encoded lower Q stream 222. Since the TCM encoder 114 encodes a trellis group of 28 input bits to generate 30 bits, the overall trellis coded modulation of the 64-QAM TCM encoder 114 yields a 28/30 rate.
The 64 QAM mapper 210 receives two upper streams 212 and 214 and one lower streams of the I and Q components for a total of six streams. Each of the streams includes 5 serial data bits. Since I and Q includes 3 data streams, both I and Q streams can be used to define 3 bits of data at any one time. For example, the bits I.sub.0 ', I.sub.1, and I.sub.2 define an I component while the bits Q.sub.0 ', Q.sub.1, and Q.sub.2 define a Q component.
The 3 bits of I and Q components can then used in a double mapping process to generate a QAM signal. Specifically, using the 3 bits of I and Q components as indices to a look-up table, the 64-QAM mapper 210 determines a QAM symbol defined by "X" and "Y" components. Each of the "X" and "Y" components is 3 bits and represent 8-PAM signal constellation. Prior Art FIG. 2B illustrates a 64-QAM table that can be used to generate the X and Y values. The TCM encoder 114 may also include a QAM constellation mapper to generate a QAM signal. That is, the QAM constellation mapper can use the X and Y components as indices to a 64 QAM constellation mapping table to generate a corresponding QAM signal. Prior Art FIG. 2C depicts a 64-QAM constellation mapping table. Given the five consecutive bits in each of the streams 212, 214, 220, and 222 of the I and Q components, this double mapping process generates 5 consecutive QAM signals corresponding to the 5 consecutive QAM symbols.
In addition to the 64-QAM encoding, the ITU-T Recommendation also specifies utilizing a 256-QAM encoding in the cable modem specification. Prior Art FIG. 3A illustrates a block diagram of a conventional 256-QAM TCM encoder 300. Unlike the 64-QAM TCM encoder, which encodes 4 symbols of 28 bits, the 256-QAM TCM encoder 300 encodes a trellis group of 38 bits into five consecutive 256-QAM symbols for mapping into five consecutive 64 QAM signals. The 256-QAM TCM encoder encodes the 38 input bits into 5 consecutive QAM symbols and signals.
The 256-QAM TCM encoder 300 serially receives 128 7-bit FEC frames (e.g., packets). A parser 302 identifies a trellis group of 38 bits and assigns 19 bits as in-phase "I" component and the remaining 19 bits as quadrature "Q" component. The trellis group of 38 bits may either be in a non-sync trellis group bit order as indicated in row 304 or a sync trellis group bit order as indicated in row 306. To form a trellis group from RS codeword symbols, the parser 302 serializes the RS symbol bits beginning with the most significant bits of the first symbol of the first RS codeword following the frame sync. Bits are then placed in trellis group locations from RS symbols in the order as indicated in rows 304 or 306. For the sync trellis group, RS bits begin at location I.sub.1 instead of I.sub.0.
In this parsing scheme, the parser 302 assigns the individual bits of the I and Q symbols RS symbols into two groups as follows: three upper or most significant uncoded bit streams 308 and 310 and one lower or least significant bit coded bit stream 312 and 314. For the I component, the parser 302 outputs three upper uncoded bit streams 308: one stream including bits I.sub.3, I.sub.7, I.sub.11, I.sub.15, and I.sub.18, another stream including bits I.sub.2, I.sub.6, I.sub.10, I.sub.14, and I.sub.17, and the remaining stream including bits I.sub.1, I.sub.5, I.sub.9, I.sub.13, and I.sub.16. For the lower coded bit stream 312 of the I component, the parser 302 outputs the bits I.sub.0, I.sub.4, I.sub.8, and I.sub.12 for transmission to a differential encoder 316. In case of the sync trellis group, the lower coded I component bit stream 312 includes S.sub.0, S.sub.2, S.sub.4, and S.sub.6.
Similarly for the Q component, the parser 302 outputs three upper uncoded bit streams 310: one stream including bits Q.sub.3, Q.sub.7, Q.sub.11, Q.sub.15, and Q.sub.18, another stream including bits Q.sub.2, Q.sub.6, Q.sub.10, Q.sub.14, and Q.sub.17, and the remaining stream including bits Q.sub.1, Q.sub.5, Q.sub.9, Q.sub.13, and Q.sub.16. For the lower coded bit stream 314 of the Q component, the parser 302 outputs the bits Q.sub.0, Q4, Q.sub.8, and Q.sub.12 for transmission to the differential encoder 316. In the case of the sync trellis group, the lower coded Q component bit stream 314 includes bits S.sub.1, S.sub.3, S.sub.5, and S.sub.7. The three upper uncoded bit streams 308 and 310 of I and Q components are transmitted to a 256-QAM mapper 318.
With reference still to Prior Art FIG. 3A, the differential encoder 316 receives the lower streams 312 and 314 of I and Q components in sequence and performs a 90 degree rotationally invariant trellis coding for each corresponding pair of I and Q bits as received. Specifically, the differential encoder 316 performs the rotationally invariant trellis coding for the I and Q bit pairs as they are received as follows: I.sub.0 and Q.sub.0, I.sub.4 and Q.sub.4, I.sub.8 and Q.sub.8, and I.sub.12 and Q.sub.12 for a non-sync trellis group bit order and S.sub.0 and S.sub.1, S.sub.2 and S.sub.3, S.sub.4 and S.sub.5, and S.sub.6 and S.sub.7 for a sync trellis group bit order. This allows the information to be carried by the change in phase, rather than by the absolute phase. The differential encoder 316 then transmits the differentially encoded lower stream I and Q components to a pair of punctured binary convolutional encoders 320 and 322, respectively.
The punctured binary convolutional encoders 320 and 322 are rate 1/2 binary convolutional encoders and convolutionally encodes redundancy into the least significant bits of the I and Q symbols to improve signal-to-noise gain. The convolutional encoders 320 and 322 are 16-state non-systematic 1/2 rate encoders with the generator: G1=010 101 and G2=011 111 (25, 37) octal. This generator is equivalent to the generator matrix [1.sym.D.sup.2.sym.D.sup.4, 1.sym.D.sym.D.sup.2.sym.D.sup.3.sym.D.sup.4 ], where D represents a delay element "Z.sup.-1." The 1/2 rate encoder generates 8 output bits from the four input bits for each I and Q component streams 312 and 314.
The 8 output bits are then fed into a puncture matrix: 0001 1111, where "0" denotes NO transmission and "1" represents transmission of the output signal. The puncture matrix essentially converts the rate 1/2 encoder to rate 4/5 to produce a single serial bit stream of 5 bits. Accordingly, the punctured binary convolutional encoders 320 and 322 encodes the 4 bits of the lower I and Q bit streams 216 and 218, respectively, to generate 5 coded bits of I.sub.0 ', I.sub.1 ', I.sub.2 ', I.sub.3 ', and I.sub.4 ' as the convolutionally encoded lower I stream 324 and 5 coded bits of Q.sub.0 ', Q.sub.1 ', Q.sub.2 ', Q.sub.3 ', and Q.sub.4 ' as the convolutionally encoded lower Q stream 326. Since the TCM encoder 300 encodes a trellis group of 38 input bits to generate 40 bits, the overall trellis coded modulation of the 256-QAM TCM encoder 300 yields a 38/40 rate.
The 256 QAM mapper 318 receives three upper streams 308 and 310 and the lower streams 324 and 326 of the I and Q components for a total of six streams. Each of the streams includes 5 serial data bits. Since I and Q each includes 4 data streams, both I and Q streams can be used to define 4 bits of data at any one time. For example, the bits I.sub.0 ', I.sub.1, I.sub.2, and I.sub.3 define an I component while the bits Q.sub.0 ', Q.sub.1, Q.sub.2, and Q.sub.3 define a Q component.
The 4 bits of I and Q components can then used in a double mapping process to generate a QAM signal. Specifically, using the 4 bits of I and Q components as indices to a look-up table, the 256-QAM mapper 318 determines an 8-bit QAM symbol defined by "X" and "Y" components. Each of the "X" and "Y" components is 4 bits and represents 16-PAM signal constellation. Prior Art FIG. 3B illustrates a 256-QAM table that can be used to generate the X and Y values. The TCM encoder 300 may also include a QAM constellation mapper 328 to generate a QAM signal. That is, the QAM constellation mapper 328 can use the X and Y components as indices to a 256 QAM constellation mapping table to generate a corresponding QAM signal. Prior Art FIG. 3C depicts a 256-QAM constellation mapping table. Given the five consecutive bits in each of the streams 308, 310, 324, and 326 of the I and Q components, this double mapping process generates 5 consecutive QAM signals corresponding to the 5 consecutive 8-bit QAM symbols.
Conventional techniques and apparatus for decoding the 64/256-QAM TCM encoded data stream would typically require direct product of two 8-state trellis and two 16-state trellis for 64- and 256-QAM TCM encoded data, respectively. This is because both the quadrature and in-phase components of demodulated 64/256-QAM signals are needed to compute the squared Euclidian distance. Hence, the conventional technique and apparatus requires the use of a heavily connected 64 or 256-state trellis, resulting in complex trellis and branch metric processing.
Thus, what is needed is an apparatus and method for recovering information bits from the 64/256-QAM TCM encoded data stream using less trellis and branch metrics.